//
//  Problem1781.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/29.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1781. 所有子字符串美丽值之和
 一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。

 比方说，"abaacc" 的美丽值为 3 - 1 = 2 。
 给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。

 示例 1：
     输入：s = "aabcb"
     输出：5
     解释：美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一个字符串的美丽值都为 1 。
 示例 2：
     输入：s = "aabcbaa"
     输出：17
 提示：
     1 <= s.length <= 500
     s 只包含小写英文字母。
 */
@objcMembers class Problem1781: NSObject {
    func solution() {
        print(beautySum("aabcb"))
        print(beautySum("aabcbaa"))
    }
    
    /*
     计算所有的字符的个数
     字符串len
     len == 1 ：最高是1，最低是1 美丽值 = 0， 不满足
     len == 2 ：aa 最高是2，最低是2 美丽值 = 0， 不满足
                ab 最高是1，最低是1 美丽值 = 0， 不满足
     所以至少len=3
     len == 3 : abc 如果3个字符都相等 = 0
                abb 2个字符相等 = 1
                aaa 3个相等 = 0
     
     1: 遍历每一个子串（>=3）
     2: 从i=0开始，[0,2][0,3][0,4]...
     3: i=1 [1,3][1,4]....
     4: i=n-3 [n-3,n-1]
     */
    func beautySum(_ s: String) -> Int {
        if s.count < 3 {
            return 0
        }
        
        var result = 0
        var dic:[Character: Int] = [:]
        let charts = Array(s)
        for i in 0...charts.count-3 {
            dic.removeAll()
            dic[charts[i], default: 0] += 1
            dic[charts[i+1], default: 0] += 1
            for j in i+2..<charts.count {
                dic[charts[j], default: 0] += 1
                let array = dic.values
                result += array.max()! - array.min()!
            }
        }
        return result
    }
}
